286E - Ladies' Shop - CodeForces Solution

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vector<int>>;

const int OO = 1e9 + 5;
const int N = 2e5 + 5;


using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> &a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd &x: a)
            x /= n;
    }
}

vl multiply(vl const &a, vl const &b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vl result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

void TC() {
    // observations:
    // 1. item weights must be a subset of bag weights,
    // as otherwise the item will form a set on its own which must exist in a bag

    // 2. all bag weights must be representable as a sum of two other bag weights,
    // as otherwise, the subset of size > 2 needed will have a subset of it with some bags that is not present

    // 3. If a bag can be constructed from two other bags, its weight is not needed as an item
    int n, m;
    cin >> n >> m;
    vl w(m+1);
    int x;
    w[0]++;
    for(int i=1; i<=n; ++i){
        cin >> x;
        w[x]++;
    }

    vl res = multiply(w, w);
    set<int> st;
    bool can = true;
    for(int i=1; i<=m; ++i){
        if(res[i]){
            if(!w[i]){
                can = false;
                break;
            }
            assert(res[i] != 1);
            if(res[i] == 2)
                st.insert(i);
        }
        else
            assert(!w[i]);
    }

    if(can){
        cout << "YES\n";
        cout << st.size() << "\n";
        for(auto e:st)
            cout << e << " ";
        cout << "\n";
    }
    else
        cout << "NO\n";





}

int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    Hagry
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
//        cout << '\n';
    }
    return 0;
}